Ćwiczenia/4. Ćwiczenia/Zadanie 3. (Liniowe sprawdzanie, czy dwa słowa są anagramami).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Proszę zaproponować algorytm, który mając dane dwa słowa $ A $ i $ B $ o długości $ n $, każde nad alfabetem długości $ k $, sprawdza, czy $ A $ i $ B $ są swoimi anagramami."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Proszę zaproponować rozwiązanie działające w czasie $ O(n + k) $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Proszę zaproponować rozwiązanie działające w czasie $ O(n) $ (proszę zwrócić uwagę, że $ k $ może być dużo większe od $ n $ — np. dla alfabetu unicode; złożoność pamięciowa może być rzędu $ O(n + k) $)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Proszę zaimplementować oba algorytmy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. podpunkt\n",
    "##### Algorytm o złożoności obliczeniowej $ O(n + k) $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Idea algorytmu jest taka, aby w tablicy długości $ k $, której indeksy odpowiadają numerom (pomniejszonym o wartość pierwszego znaku alfabetu - uznajemy, że alfabet jest tworzony przez kolejne znaki UNICODE, a więc np. pomiędzy każdymi dwiema literami danego alfabetu nie znajduje się żaden znak, który nie należy do tego alfabetu) UNICODE odpowiednich znaków alfabetu, przechowywać liczniki wartości. Ponieważ anagramy to słowa tej samej długości, zbudowane z tej samej liczby takich samych znaków, w których różni się jedynie kolejność tych znaków (jedno słowo powtało poprzez permutację liter drugiego słowa), wystarczy nam policzyć ile danych liter posiada każde słowo i odpowiednio zwiększać licznik, jeżeli pierwsze słowo zawiera daną literę oraz zmniejszać licznik, jeżeli drugie słowo posiada daną literę (można odwrotnie). Na koniec wystarczy przebiec liniowo po tablicy liczników długości $ k $ i sprawdzać, czy licznik na każdym z pól ma wartość $ 0 $ (tzn. oba słowa zawierają tyle samo znaków o danym kodzie). Jeżeli natrafimy na liczbę różną od $ 0 $, oznacza to, że słowa nie są anagramami, w przeciwnym razie, po zakończniu przebiegu bez przerwania pętli, słowa są anagramami."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Warto nadmienić, że złożoność pamięciowa w tym przypadku również wynosi $ O(n + k) $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def are_anagrams(s1, s2):\n",
    "    # Words of different lengths cannot be anagrams\n",
    "    if len(s1) != len(s2): return False\n",
    "    # Find the maximum and the minimum value of the UNICODE code\n",
    "    # of the letters in both strings and create an array of to store counters\n",
    "    # (It's essential to know the code of the letter from boths strings which\n",
    "    # appears in an alphabet first in order to access the indices of counts\n",
    "    # array properly (as we are not given a char code of the first letter of an\n",
    "    # alphabet)) (maximum value is not required as we know how many letters\n",
    "    # there are in an alphabet but this ensures that we won't create redundant\n",
    "    # array slots).\n",
    "    s1_min_char, s1_max_char = minmax(s1)\n",
    "    s2_min_char, s2_max_char = minmax(s2)\n",
    "    min_char_ord = min(ord(s1_min_char), ord(s2_min_char))\n",
    "    max_char_ord = min(ord(s1_max_char), ord(s2_max_char))\n",
    "    # Allocate memory for counters\n",
    "    counters = [0] * (max_char_ord - min_char_ord + 1)\n",
    "    \n",
    "    # Loop over both strings and increment or decrement appropriate counters\n",
    "    for char in s1: counters[ord(char) - min_char_ord] += 1\n",
    "    for char in s2: counters[ord(char) - min_char_ord] -= 1\n",
    "        \n",
    "    # Loop over a counters array and check if all counters are set to 0\n",
    "    for counter in counters:\n",
    "        # If is non-zero, return False as words cannot be anagrams\n",
    "        if counter: return False\n",
    "    # If a loop above has finished, return True\n",
    "    return True\n",
    "    \n",
    "    \n",
    "def minmax(iterable):\n",
    "    # We assume that an iterable supports indexing (to handle sets or dictionaries\n",
    "    # iteration we can use an iterator object but in this example this is overkill).\n",
    "    # Store the last value in order to ease odd-length iterable values comparisons.\n",
    "    max_val = min_val = iterable[-1]  \n",
    "    \n",
    "    for i in range(1, len(iterable), 2):\n",
    "        if iterable[i] > iterable[i-1]:\n",
    "            if iterable[i] > max_val:   max_val = iterable[i]\n",
    "            if iterable[i-1] < min_val: min_val = iterable[i-1]\n",
    "        else:\n",
    "            if iterable[i] < min_val:   min_val = iterable[i]\n",
    "            if iterable[i-1] > max_val: max_val = iterable[i-1]\n",
    "                \n",
    "    # Return the minimum and the maximum value\n",
    "    return min_val, max_val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "True\n",
      "True\n",
      "True\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "print(are_anagrams('aaaa', 'aaaa'))\n",
    "print(are_anagrams('aaaa', 'aaaaa'))\n",
    "print(are_anagrams('😂', '😂'))\n",
    "print(are_anagrams('😂🤣👀🎂✨🎁', '🎂🎁😂👀✨🤣'))\n",
    "print(are_anagrams('kot', 'kto'))\n",
    "print(are_anagrams('ola ala ula ela', 'ela ala ola ula'))\n",
    "print(are_anagrams('ola ala ula ela', 'ela alaola ula'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. podpunkt\n",
    "##### Algorytm o złożoności obliczeniowej $ O(n) $ i pamięciowej maksymalnie $ O(n + k) $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## I Sposób"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "W tej implementacji zakładamy, że zaalokowanie tablicy długości $ k $ zajmuje czas $ O(1) $, jak ma to miejsce w językach, w których tablice nie są dynamiczne, np. w językach z rodziny C. Wówczas można zauważyć, że nie musimy przebiegać po załej $ k $-elementowej tablicy liczników, a jedynie wystarczy podczas aktualizowania liczników dla drugiego wyrazu, sprawdzać za każdym razem, czy licznik nie zszedł poniżej zera. Jeżeli tak, możemy zakończyć aktualizowanie liczników i zwrócić fałsz, bo już \"nie nadrobimy\" wartości (nie da się jej przywrócić do zera, bo podczas aktualizacji liczników dla drugiego wyrazu, dekrementujemy liczniki)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### UWAGA:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Warto zauważyć, że jeżeli w drugim z wyrazów będzie mniej wystąpień danego znaku niż w pierwszym wyrazie, sprawdzany przez nas warunek na zejście licznika poniżej 0 nie przerwie pętli (nie wykryjemy tego, że dana litera występuje w pierwszym wyrazie więcej razy niż w drugim). Jednakże NIE JEST TO PROBLEM, bo sprawdzamy najpierw, czy oba wyrazy mają tę samą długość. Jesteśmy więc pewni, że skoro w drugim wyrazie jest mniej wystąpień danej litery, inna litera musi wystąpić więcej razy niż w pierwszym wyrazie (tzn. nigdy nie zajdzie sytuacja, że dwa wyrazy są równej długości, ale w drugim wyrazie liczba wystąpień wszystkich liter jest mniejsza niż liczba wystąpień liter w pierwszym wyrazie). Wynika to z faktu, że nawet jeśli każde z liter wyrazu pierwszego występuje w wyrazie drugim mniej razy niż w wyrazie pierwszym, to w drugim wyrazie znajdzie się zawsze taka litera, która w pierwszym wyrazie nie występuje. Wtedy licznik dla danej litery zostanie zmniejszony z 0 do -1 i funkcja zwróci wartość fałsz."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def are_anagrams(s1, s2):\n",
    "    # Words of different lengths cannot be anagrams\n",
    "    if len(s1) != len(s2): return False\n",
    "    # Find the maximum and the minimum value of the UNICODE code\n",
    "    # of the letters in both strings and create an array of to store counters\n",
    "    # (It's essential to know the code of the letter from boths strings which\n",
    "    # appears in an alphabet first in order to access the indices of counts\n",
    "    # array properly (as we are not given a char code of the first letter of an\n",
    "    # alphabet)) (maximum value is not required as we know how many letters\n",
    "    # there are in an alphabet but this ensures that we won't create redundant\n",
    "    # array slots).\n",
    "    s1_min_char, s1_max_char = minmax(s1)\n",
    "    s2_min_char, s2_max_char = minmax(s2)\n",
    "    min_char_ord = min(ord(s1_min_char), ord(s2_min_char))\n",
    "    max_char_ord = min(ord(s1_max_char), ord(s2_max_char))\n",
    "    # Allocate memory for counters\n",
    "    counters = [0] * (max_char_ord - min_char_ord + 1)\n",
    "    \n",
    "    # Loop over both strings and increment or decrement appropriate counters\n",
    "    for char in s1: \n",
    "        counters[ord(char) - min_char_ord] += 1\n",
    "        \n",
    "    for char in s2: \n",
    "        idx = ord(char) - min_char_ord\n",
    "        counters[idx] -= 1\n",
    "        # If we decreased a counter too much (the second word thet means the second\n",
    "        # word has more letters of this code so these words cannot be anagrams).\n",
    "        if counters[idx] < 0:\n",
    "            return False\n",
    "        \n",
    "    return True\n",
    "    \n",
    "    \n",
    "def minmax(iterable):\n",
    "    # We assume that an iterable supports indexing (to handle sets or dictionaries\n",
    "    # iteration we can use an iterator object but in this example this is overkill).\n",
    "    # Store the last value in order to ease odd-length iterable values comparisons.\n",
    "    max_val = min_val = iterable[-1]  \n",
    "    \n",
    "    for i in range(1, len(iterable), 2):\n",
    "        if iterable[i] > iterable[i-1]:\n",
    "            if iterable[i] > max_val:   max_val = iterable[i]\n",
    "            if iterable[i-1] < min_val: min_val = iterable[i-1]\n",
    "        else:\n",
    "            if iterable[i] < min_val:   min_val = iterable[i]\n",
    "            if iterable[i-1] > max_val: max_val = iterable[i-1]\n",
    "                \n",
    "    # Return the minimum and the maximum value\n",
    "    return min_val, max_val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "True\n",
      "True\n",
      "True\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "print(are_anagrams('aaaa', 'aaaa'))\n",
    "print(are_anagrams('aaaa', 'aaaaa'))\n",
    "print(are_anagrams('😂', '😂'))\n",
    "print(are_anagrams('😂🤣👀🎂✨🎁', '🎂🎁😂👀✨🤣'))\n",
    "print(are_anagrams('kot', 'kto'))\n",
    "print(are_anagrams('ola ala ula ela', 'ela ala ola ula'))\n",
    "print(are_anagrams('ola ala ula ela', 'ela alaola ula'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## II Sposób"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "W tym sposobie zakładamy, że tablica na kolejne znaki alfabetu jest już odgórnie zaalokowana i akceptuje wszystkie znaki alfabetu UNICODE. Ponieważ nie mamamy danego kodu pierwszego znaku alfabetu, alokujemy od razu globalną tablicę na wszystkie możliwe przypadki. Ten algorytm jest najgorszy, jeżeli chodzi o złożoność pamięciową, ale mamy powiedziane w 2. podpunkcie, że pamięć nie ma znaczenia (fragment: \"$ k $ może być dużo większe od $ n $ — np. dla alfabetu unicode\" oraz fragment: \"złożoność pamięciowa może być rzędu $ O(n + k) $\"). Czyli złożoność pamięciowa nas nie obchodzi. Jeżeli chodzi o złożoność obliczeniową, to jest ona tu najlepsza, ponieważ nie musimy szukać znaku o największym oraz znaku u najmniejszym kodzie UNICODE, jak miało to miejsce wyżej (mamy około $ \\frac{3}{2}n \\cdot 2 \\cdot c = 3nc $ mniej porównań, gdzie $ c $ - pewna stała, bo funkcja $ minmax $ działa ze złożonością $ O(\\frac{3}{2}n) = O(n) $). Musimy zatem pamiętać o wyzerowaniu liczników najpierw, co zajmie nam ok. $ O(2n \\cdot c) = O(n) $ operacji (wystarczy nam zerowanie dla jednego wyrazu). Wynika to z faktu, iż tablica jest odgórnie zaalokowana i mogą w niej być pozostałości po poprzednich porównaniach wyrazów (oraz w innych językach programowania zazwyczaj tworzenie tablicy odbywa się jedynie jako utworzenie wskaźnika do pierwszego elementu bez inicjalizacji kolejnych slotów, więc występują na nich losowe wartości)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Implementacja klasy pomocniczej, która \"udaje\" alokowanie tablicy, działające podobnie do języków z rodziny C."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def rand_int(bits=16):\n",
    "    return random.randint(0, 2 ** bits)\n",
    "\n",
    "class Array:\n",
    "    def __init__(self, size):\n",
    "        self.values = [rand_int() for _ in range(size)]\n",
    "        \n",
    "    def __getitem__(self, idx):\n",
    "        if 0 <= idx < len(self.values):\n",
    "            return self.values[idx]\n",
    "        # Imitate access to the index beyond of an the array\n",
    "        return rand_int()\n",
    "    \n",
    "    def __setitem__(self, idx, val):\n",
    "        if 0 <= idx < len(self.values):\n",
    "            self.values[idx] = val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Właściwy algorytm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def are_acronyms_init():\n",
    "    # Allocate a memory for the whole UNICODE alphabet (only once)\n",
    "    # as nonlocal variable accessible by the inner function only.\n",
    "    counts = Array(2 ** 16)\n",
    "    \n",
    "    # Return a function which will be used to compare strings\n",
    "    def are_acronyms(s1, s2):\n",
    "        if len(s1) != len(s2): return False\n",
    "        # Fill the necessary counters with zeros (we don't have\n",
    "        # to do this for boths strings)\n",
    "        for char in s1: counts[ord(char)] = 0\n",
    "            \n",
    "        # Increment counters for characters in the first string\n",
    "        for char in s1: counts[ord(char)] += 1\n",
    "        # Decrement counters for characters in the second string\n",
    "        for char in s2: counts[ord(char)] -= 1\n",
    "        \n",
    "        # Check if all counters of the first string characters are\n",
    "        # equal to 0. Note that we don't have to check counters for\n",
    "        # the second string separately as we checked if both strings\n",
    "        # are of the same lengths before. If they do so, the second\n",
    "        # string cannot have all the characters repeated the same number\n",
    "        # of times as the first one and some other characters as lengths\n",
    "        # of the strings will not be the same.\n",
    "        for char in s1:\n",
    "            if counts[ord(char)] != 0:\n",
    "                return False\n",
    "        # Return True if all the counters of characters on the first string\n",
    "        # are set to zero.\n",
    "        return True\n",
    "        \n",
    "    return are_acronyms\n",
    "\n",
    "\n",
    "are_acronyms = are_acronyms_init()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "True\n",
      "True\n",
      "True\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "print(are_anagrams('aaaa', 'aaaa'))\n",
    "print(are_anagrams('aaaa', 'aaaaa'))\n",
    "print(are_anagrams('😂', '😂'))\n",
    "print(are_anagrams('😂🤣👀🎂✨🎁', '🎂🎁😂👀✨🤣'))\n",
    "print(are_anagrams('kot', 'kto'))\n",
    "print(are_anagrams('ola ala ula ela', 'ela ala ola ula'))\n",
    "print(are_anagrams('ola ala ula ela', 'ela alaola ula'))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}